import java.util.*;

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = 10010;
        int[] tmp = new int[n];
        for(int x : nums) { tmp[x] += x;}
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        for(int i = 1; i <= n; i++){
            f[i] = tmp[i - 1] + g[i - 1];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[n], g[n]);
    }

    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n + 1][3];

        for(int i = 1; i <= n; i++){
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        return Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2]));
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n + 1][3];
        dp[0][0] = - prices[0];

        for(int i = 1; i <= n; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i - 1]);
            dp[i][1] = dp[i - 1][0] + prices[i - 1];
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
        }
        return Math.max(dp[n][1], dp[n][2]);
    }

    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n + 1][2];
        dp[0][0] = - prices[0];

        for(int i = 1; i <= n; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i - 1]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1] - fee);
        }
        return dp[n][1];
    }

    public int DiffmaxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        for(int j = 0; j < 3; j++) {
            f[0][j] = -0x3f3f3f3f;
            g[0][j] = -0x3f3f3f3f;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j <= 2; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0){
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        return Math.max(g[n - 1][0], Math.max(g[n - 1][1], g[n - 1][2]));
    }

    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        k = Math.min(k, n / 2);
        int[][] f = new int[n][k + 1];
        int[][] g = new int[n][k + 1];
        for(int j = 0; j <= k; j++){
            f[0][j] = -0x3f3f3f3f;
            g[0][j] = -0x3f3f3f3f;
        }
        f[0][0] = - prices[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j <= k; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0){
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int ret = 0;
        for(int j = 0; j <= k; j++){
            ret = Math.max(ret, g[n - 1][j]);
        }
        return ret;
    }

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];

        int ret = - Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        int sum = 0, fmax = Integer.MIN_VALUE, gmin = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            f[i] = Math.max(nums[i - 1], f[i - 1] + nums[i - 1]);
            fmax = Math.max(fmax, f[i]);
            g[i] = Math.min(nums[i - 1], g[i - 1] + nums[i - 1]);
            gmin = Math.min(gmin, g[i - 1]);
            sum += nums[i - 1];
        }

        return sum == gmin ? fmax : Math.max(fmax, sum - gmin);
    }

    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = g[0] = 1;

        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1];
            f[i] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }

    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            if(nums[i - 1] > 0){
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }else if(nums[i - 1] < 0){
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }

    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];

        int sum = 0;
        for(int i = 3; i <= n; i++){
            dp[i] = nums[i - 1] - nums[i - 2] == nums[i - 2] -nums[i - 3] ? dp[i - 1] + 1 : 0;
            sum += dp[i];
        }
        return sum;
    }

    public int maxTurbulenceSize(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        for(int i = 0; i <= n; i++){
            f[i] = g[i] = 1;
        }

        int ret = 1;
        for(int i = 2; i <= n; i++){
            if(nums[i - 2] < nums[i - 1]) { f[i] = g[i - 1] + 1;}
            if(nums[i - 2] > nums[i - 1]) { g[i] = f[i - 1] + 1;}
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hash = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        s = " " + s;

        for(int i = 1; i <= n; i++){
            for(int j = i; j >= 1; j--){
                if(dp[j - 1] && hash.contains(s.substring(j, i + 1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();

        int[] dp = new int[n];
        for(int i = 0; i < n; i++) { dp[i] = 1;}

        for(int i = 1; i < n; i++){
            if(ch[i] - ch[i - 1] == 1 || ch[i] == 'a' && ch[i - 1] == 'z'){
                dp[i] += dp[i - 1];
            }
        }

        int[] hash = new int[26];
        for(int i = 0; i < n; i++){
            hash[ch[i] - 'a'] = Math.max(hash[ch[i] - 'a'], dp[i]);
        }

        int sum = 0;
        for(int x : hash) { sum += x;}
        return sum;
    }

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        System.out.println(wordBreak(s,wordDict));
    }
}